백준 2098번
오늘 풀어본 문제는 백준의 2098번 문제1이다. 문제 풀이에 사용한 언어는 C++ 이다.
solved.ac 기준 CLASS
문제 정보
이 문제의 내용과 조건은 다음과 같다.
문제
외판원 순회 문제는 영어로 Traveling Salesman problem (TSP) 라고 불리는 문제로 computer science 분야에서 가장 중요하게 취급되는 문제 중 하나이다. 여러 가지 변종 문제가 있으나, 여기서는 가장 일반적인 형태의 문제를 살펴보자.
$1$ 번부터 $N$ 번까지 번호가 매겨져 있는 도시들이 있고, 도시들 사이에는 길이 있다. (길이 없을 수도 있다) 이제 한 외판원이 어느 한 도시에서 출발해 $N$ 개의 도시를 모두 거쳐 다시 원래의 도시로 돌아오는 순회 여행 경로를 계획하려고 한다. 단, 한 번 갔던 도시로는 다시 갈 수 없다. (맨 마지막에 여행을 출발했던 도시로 돌아오는 것은 예외) 이런 여행 경로는 여러 가지가 있을 수 있는데, 가장 적은 비용을 들이는 여행 계획을 세우고자 한다.
각 도시간에 이동하는데 드는 비용은 행렬 $W[i][j]$ 형태로 주어진다. $W[i][j]$ 는 도시 $i$ 에서 도시 $j$ 로 가기 위한 비용을 나타낸다. 비용은 대칭적이지 않다. 즉, $W[i][j]$ 는 $W[j][i]$ 와 다를 수 있다. 모든 도시간의 비용은 양의 정수이다. $W[i][i]$ 는 항상 $0$ 이다. 경우에 따라서 도시 $i$ 에서 도시 $j$ 로 갈 수 없는 경우도 있으며 이럴 경우 $W[i][j]=0$ 이라고 하자.
$N$ 과 비용 행렬이 주어졌을 때, 가장 적은 비용을 들이는 외판원의 순회 여행 경로를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 도시의 수 $N$ 이 주어진다. $(2 \le N \le 16)$ 다음 $N$ 개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 $1,000,000$ 이하의 양의 정수이며, 갈 수 없는 경우는 $0$ 이 주어진다. $W[i][j]$는 도시 $i$ 에서 $j$ 로 가기 위한 비용을 나타낸다.
항상 순회할 수 있는 경우만 입력으로 주어진다.
출력
첫째 줄에 외판원의 순회에 필요한 최소 비용을 출력한다.
풀이과정
1번째 시도
문제에서 이야기 하듯이, 이 문제는 외판원 순회로 알려진 문제이다. DP 를 이용하여 문제해결을 시도하였다.
코드는 다음과 같이 작성하였다.
#include <bits/stdc++.h>
using namespace std;
int N;
vector<vector<int>> graph(16, vector<int>(16, 0));
vector<vector<int>> dp(16, vector<int>(1 << 16, INT_MAX));
int TSP(int start, unsigned visited);
int main(void) {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> N;
for (int i=0; i<N; i++) {
for (int j=0; j<N; j++) {
int temp;
cin >> temp;
if (temp == 0) {
graph[i][j] = INT_MAX;
}
else {
graph[i][j] = temp;
}
}
}
cout << TSP(0, 1);
return 0;
}
int TSP(int start, unsigned visited) {
if (visited == (1 << N) - 1) {
dp[start][visited] = graph[start][0];
return graph[start][0];
}
else if (dp[start][visited] != INT_MAX) {
return dp[start][visited];
}
else {
for (int i=1; i<N; i++) {
if (visited & (1 << i)) {
continue;
}
else {
int otherWay = TSP(i, visited | (1 << i));
dp[start][visited] = min(dp[start][visited], otherWay + graph[start][i]);
}
}
return dp[start][visited];
}
}
실행 결과 ‘틀렸습니다’ 가 떴다.
2번째 시도
틀린 이유를 조사해본 결과, INT_MAX 를 쓰는 과정에서 오버플로우가 난 듯 했다. 맨날 당하는 일인데도 기억을 잘 못하는 것 같다… 어쨌든 INT_MAX 대신 다른 수를 이용하기로 하였다.
코드는 다음과 같이 수정하였다.
#define INF 987654321
#include <bits/stdc++.h>
using namespace std;
int N;
vector<vector<int>> graph(16, vector<int>(16, 0));
vector<vector<int>> dp(16, vector<int>(1 << 16, INF));
int TSP(int start, unsigned visited);
int main(void) {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> N;
for (int i=0; i<N; i++) {
for (int j=0; j<N; j++) {
cin >> graph[i][j];
}
}
cout << TSP(0, 1);
return 0;
}
int TSP(int start, unsigned visited) {
if (visited == (1 << N) - 1) {
if (graph[start][0] != 0) {
dp[start][visited] = graph[start][0];
}
}
else if (dp[start][visited] == INF) {
for (int i=1; i<N; i++) {
if (visited & (1 << i) || graph[start][i] == 0) {
continue;
}
else {
dp[start][visited] = min(dp[start][visited], TSP(i, visited | (1 << i)) + graph[start][i]);
}
}
}
return dp[start][visited];
}
실행 결과 ‘시간 초과’ 가 떴다.
3번째 시도
시간 초과가 발생한 원인을 조사한 결과 이미 확인한 경우를 또 다시 확인하는 경우가 있었고, 이를 해결하기 위해 caseChecked 라는 변수를 도입하여 특정 상황을 이미 검사하였는지 저장하도록 하였다.
코드는 다음과 같이 수정하였다.
#define INF 987654321
#include <bits/stdc++.h>
using namespace std;
int N;
vector<vector<int>> graph(16, vector<int>(16, 0));
vector<vector<int>> dp(16, vector<int>(1 << 16, INF));
vector<vector<bool>> caseChecked(16, vector<bool>(1 << 16, false));
int TSP(int start, unsigned visited);
int main(void) {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> N;
for (int i=0; i<N; i++) {
for (int j=0; j<N; j++) {
cin >> graph[i][j];
}
}
cout << TSP(0, 1);
return 0;
}
int TSP(int start, unsigned visited) {
if (!caseChecked[start][visited]) {
caseChecked[start][visited] = true;
if (visited == (1 << N) - 1) {
if (graph[start][0] != 0) {
dp[start][visited] = graph[start][0];
}
}
else if (dp[start][visited] == INF) {
for (int i=1; i<N; i++) {
if (visited & (1 << i) || graph[start][i] == 0) {
continue;
}
else {
dp[start][visited] = min(dp[start][visited], TSP(i, visited | (1 << i)) + graph[start][i]);
}
}
}
}
return dp[start][visited];
}
그러자 모든 테스트 케이스를 통과하고 정답이 나오는 것을 확인할 수 있었다.
마무리
이 문제에선 생각하지 못했던 부분이 많았다. 꽤나 사람 지치게 하는 문제였다… CLASS 5 문제들은 하나하나 충분한 시간을 들여야 풀 수 있는 문제인 것 같다. CLASS 6 에서는 대체 뭐가 나오려나…
오늘의 PS는 여기까지!
1: https://www.acmicpc.net/problem/2098